/*
Maximal Rectangle Total Accepted: 28947 Total Submissions: 131229 My Submissions Question Solution
Given a 2D binary matrix filled with 0's and 1's, find the largest rectangle containing all ones and return its area.


*/
#include <iostream>
#include "print.h"
#include <vector>
#include <map>
#include <stack>
#include <algorithm>

using namespace std;


/***/
//Definition for an interval.
struct Interval {
	int start;
	int end;
	Interval() : start(0), end(0) {}
	Interval(int s, int e) : start(s), end(e) {}
};
class Solution {
public:

	int largestRectArea(vector<int> &nums)
	{
		stack<int> stk;
		int i = 0;
		int maxArea = 0;
		nums.push_back(0);
		while (i < nums.size())
		{
			if (stk.empty() || nums[stk.top()] <= nums[i])
			{
				stk.push(i++);
			}
			else
			{
				int t = stk.top();
				stk.pop();
				int temp = nums[t] * (stk.empty() ? i : i - stk.top() - 1);
				maxArea = maxArea > temp ? maxArea : temp;

			}

		}
		return maxArea;
	
	}


	int maximalRectangle(vector<vector<char>>& matrix) {

		if (matrix.size()==0)
		{
			return 0;
		}
		int row = matrix.size();
		int col = matrix[0].size();
		if (col == 0)
		{
			return 0;
		}

		vector<int> rows(col, 0);
		vector<vector<int> > dicts(row, rows);

		for (int j = 0; j < col; j++)
		{
			if (matrix[0][j] == '1')
			{
				dicts[0][j] = 1;
			}
		}

		for (int j = 0; j < col; j++)
		{
			for (int i = 1; i < row; i++)
			{
				if (matrix[i][j] == '1')
				{
					dicts[i][j] = dicts[i - 1][j] + 1;
				}
			}

		}


		int maxArea = 0;
		for (int i = 0; i < row; i++)
		{
			int curArea = largestRectArea(dicts[i]);
			if (maxArea < curArea)
			{
				maxArea = curArea;
			}
		}

		return maxArea;
	}
};




int main()
{
	int a[] = { 2, 1, 5, 6, 2, 3 };
	vector<int> nums(a, a + sizeof(a) / sizeof(int));

	char b[] = { '1'};
	vector<char> rows(b,b+sizeof(b)/sizeof(char));

	vector<vector<char>> dicts;

	dicts.push_back(rows);

	Solution s;

	int res = s.maximalRectangle(dicts);


	system("pause");
	return 0;
}